package cn.zifangsky.tree.binarytree.questions;

import org.junit.Test;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;
import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 逆向逐层输出二叉树中的每个元素
 * @author zifangsky
 *
 */
public class Question7 {
	
	/**
	 * 逆向逐层输出二叉树中的每个元素
	 * 思路：
	 * 		如果只是顺序逐层输出，则只需要使用队列辅助做层次遍历即可。但是因为要求是“逆向逐层输出”因此可以考虑使用栈辅助操作。
	 * 也就是在使用队列逐层遍历时，在队列元素出队的时候将元素压入栈中，最后将栈中的所有元素都出栈遍历即可。
	 * 但是这样做的一个问题就是最后输出是从右往左输出（PS：因为左子树比右子树先入队，也将先出队和先入栈），因此在将入队时让右子树比
	 * 左子树先入队即可解决这个问题
	 * @时间复杂度 O(n)
	 * @param root
	 */
	public void levelOrderInReverse(BinaryTreeNode<Integer> root){
		Stack<Integer> stack = new LinkStack<>();
		Queue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.push(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> temp = queue.pop(); //出队
			stack.push(temp.getData()); //数据入栈
			
			//左孩子节点先入队，右孩子节点后入队
			if(temp.getRight() != null){
				queue.push(temp.getRight());
			}
			if(temp.getLeft() != null){
				queue.push(temp.getLeft());
			}
		}
		
		while (!stack.isEmpty()) {
			System.out.print(stack.pop() + " ");
		}
	}

	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		/**
		 * 使用队列构造一个供测试使用的二叉树
		 *     1
		 *   2    3
		 * 4  5  6  7
		 *   8 9  
		 */
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		
		queue.push(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> tmpNode2 = new BinaryTreeNode<>(i+1);
			
			temp = queue.pop();
			
			temp.setLeft(tmpNode1);
			temp.setRight(tmpNode2);
			
			if(i != 4)
				queue.push(tmpNode1);
			queue.push(tmpNode2);
		}

		System.out.println("遍历的结果是： ");
		levelOrderInReverse(root);

	}

}
